package com.sheyu;

import java.util.*;

/**
 * @author sheyu
 * @date 2020/8/26 9:26 上午
 */
public class Index_20 {
    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 注意空字符串可被认为是有效字符串。
     *
     * 链接：https://leetcode-cn.com/problems/valid-parentheses
     *
     * 利用map存储括号的映射以便判断结果
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        Map<Character,Character> map = new HashMap<>();
        Deque<Character> deque = new ArrayDeque<>();
        map.put('[',']');
        map.put('{','}');
        map.put('(',')');
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (map.containsKey(c)){
                deque.push(map.get(c));
            }else{
                if(deque.size()>0&&deque.peekFirst().equals(c)){
                    deque.pop();
                }else{
                    return false;
                }
            }
        }
        return deque.isEmpty();
    }
/*
    class Solution {
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            Map<Character,Character> map = new HashMap<>();
            map.put('{','}');
            map.put('[',']');
            map.put('(',')');
            for(int i=0;i<s.length();i++){
                if(s.charAt(i) == '{' || s.charAt(i) == '[' || s.charAt(i) == '('){
                    stack.push(s.charAt(i));
                }else{
                    if (stack.size()==0){
                        return false;
                    }
                    else if (s.charAt(i) == map.get(stack.pop())){
                        continue;
                    }else{
                        return false;
                    }
                }
            }
            return stack.size()==0;
        }
    }*/
    public static void main(String[] args) {
        System.out.println(isValid("(){]"));
    }
}
